package com.zjj.learn.algorithmPlus.segment1.priorityQueue;

import com.zjj.learn.algorithmPlus.segment1.queue.Queue;

/**
 * <p>
 * 基于有序数组实现优先级队列
 * 使用有序数组，优先级高的数据存放在数组的最后，每一次获取数据时直接那数组中最后一个数据即可。
 * 这样在获取数据时比较简单，进而添加数据时就比较复杂了。需要将插入数据存放在合适的位置。
 *
 * @author zjj_admin
 */
public class ArrayPriorityQueue2<E extends Priority> implements Queue<E> {


    private final Priority[] array;
    private int size;

    public ArrayPriorityQueue2(int capacity) {
        size = 0;
        array = new Priority[capacity];
    }

    /**
     * 添加数据
     *
     * @param value 添加数据
     * @return
     */
    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        // 从后向前找，获取第一个优先级小于插入数据的下标索引
        int target = getTargetIndex(value.priority());
        if (target == 0) {
            // 当 target = 0 时，将所有的数据整体后移动一位
            System.arraycopy(array, 0, array, 1, size);
            array[0] = value;
        } else {
            //从索引 target + 1 开始，将后面的数据整体向后移动一位
            // 这里也可以采用插入排序算法进行修改
            System.arraycopy(array, target + 1, array, target + 2, size - target - 1);
            array[target + 1] = value;
        }
        size++;
        return true;
    }

    /**
     * 从后向前找，获取第一个优先级小于插入数据的下标索引
     *
     * @return
     */
    private int getTargetIndex(int priority) {
        for (int i = size - 1; i >= 0; i--) {
            if (array[i].priority() < priority) {
                return i;
            }
        }
        // 最后就返第一个即可
        return 0;
    }


    /**
     * 移除并返回优先级最高的一个数据
     *
     * @return
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        //直接获取最后一个数据即可
        @SuppressWarnings("all")
        E value = (E) array[size - 1];
        //删除元素
        size--;
        return value;
    }


    /**
     * 返回优先级最高的一个数据
     *
     * @return
     */
    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        //直接获取最后一个数据即可
        @SuppressWarnings("all")
        E value = (E) array[size - 1];
        return value;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }

    @Override
    public int size() {
        return size;
    }
}
